{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hasPathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #路径总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点&nbsp;<code>root</code> 和一个表示目标和的整数&nbsp;<code>targetSum</code> 。判断该树中是否存在 <strong>根节点到叶子节点</strong> 的路径，这条路径上所有节点值相加等于目标和&nbsp;<code>targetSum</code> 。如果存在，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p><strong>叶子节点</strong> 是指没有子节点的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/pathsum1.jpg\" style=\"width: 500px; height: 356px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>等于目标和的根节点到叶节点路径如上图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3], targetSum = 5\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>树中存在两条根节点到叶子节点的路径：\n",
    "(1 --&gt; 2): 和为 3\n",
    "(1 --&gt; 3): 和为 4\n",
    "不存在 sum = 5 的根节点到叶子节点的路径。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [], targetSum = 0\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>由于树是空的，所以不存在根节点到叶子节点的路径。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[0, 5000]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li><code>-1000 &lt;= targetSum &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-sum](https://leetcode.cn/problems/path-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-sum](https://leetcode.cn/problems/path-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,8,11,null,13,4,7,2,null,null,null,1]\\n22', '[1,2,3]\\n5', '[]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if root is None: return False\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                curr = queue.popleft()\n",
    "                if curr.left is not None:\n",
    "                    curr.left.val += curr.val\n",
    "                    queue.append(curr.left)\n",
    "                if curr.right is not None:\n",
    "                    curr.right.val += curr.val\n",
    "                    queue.append(curr.right)\n",
    "                if curr.left is None and curr.right is None and curr.val == sum:\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "#     def hasPathSum(self, root, sum):\n",
    "#         \"\"\"\n",
    "#         :type root: TreeNode\n",
    "#         :type sum: int\n",
    "#         :rtype: bool\n",
    "#         \"\"\"\n",
    "#         if not root:\n",
    "#             return False\n",
    "\n",
    "#         sum -= root.val\n",
    "#         if not root.left and not root.right:  # if reach a leaf\n",
    "#             return sum == 0\n",
    "#         return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def bt(root, s, t):\n",
    "            if not root:\n",
    "                return False\n",
    "            if not root.left and not root.right and s+root.val == t:\n",
    "                return True\n",
    "            return bt(root.left, s+root.val, t) or bt(root.right, s+root.val, t)\n",
    "        return bt(root, 0, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return False\n",
    "\n",
    "        if not root.left and not root.right and root.val == sum:\n",
    "            return True\n",
    "\n",
    "        sum -= root.val\n",
    "\n",
    "        return self.hasPathSum(root.left, sum) or self.hasPathSum(\n",
    "            root.right, sum)\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(root, tar):\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == tar and root.left is None and root.right is None:\n",
    "                # print(23, res)\n",
    "                return True\n",
    "            return dfs(root.left, tar - root.val) or dfs(root.right, tar - root.val)\n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        return dfs(root, sum)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        ##BFS\n",
    "        # if root==None:\n",
    "        #     return False\n",
    "        # stack=[(root,root.val)]\n",
    "        # while stack:\n",
    "        #     root, value=stack.pop(0)\n",
    "        #     print(root.val,value)\n",
    "        #     if root.left==None and root.right==None and value==sum:\n",
    "        #         return True\n",
    "        #     if root.left:\n",
    "        #         stack.append((root.left,root.left.val+value))\n",
    "        #     if root.right:\n",
    "        #         stack.append((root.right,root.right.val+value))\n",
    "        # return False\n",
    "         ##DFS\n",
    "        if root==None:\n",
    "            return False\n",
    "        stack=[(root,root.val)]\n",
    "        while stack:\n",
    "            root, value=stack.pop()\n",
    "            print(root.val,value)\n",
    "            if root.left==None and root.right==None and value==sum:\n",
    "                return True\n",
    "            if root.left:\n",
    "                stack.append((root.left,root.left.val+value))\n",
    "            if root.right:\n",
    "                stack.append((root.right,root.right.val+value))\n",
    "        return False\n",
    "    \n",
    "   \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if not root:return False\n",
    "        if root.val ==sum and not root.left and not root.right:return True\n",
    "        else :return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root, sumv):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root is None: \n",
    "            self.Preorder(root)\n",
    "            for item in self.sumvals:\n",
    "                if sumv == item:\n",
    "                    return True        \n",
    "            return False\n",
    "        return False \n",
    "        \n",
    "        \n",
    "    def __init__(self):\n",
    "        self.TreePath=[]\n",
    "        self.sumvals=[]\n",
    "        \n",
    "        \n",
    "    def Preorder(self, root):\n",
    "        self.TreePath.append(root.val)\n",
    "        if not root.left is None:\n",
    "            self.Preorder(root.left)            \n",
    "        if not root.right is None: \n",
    "            self.Preorder(root.right)\n",
    "        if root.left is None and root.right is None: \n",
    "            self.sumvals.append(self.GetSum())\n",
    "            print(sum(self.TreePath))\n",
    "        self.TreePath.pop()  \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "    def GetSum(self):\n",
    "        sumvalue = 0\n",
    "        for i in self.TreePath:\n",
    "            sumvalue+=i\n",
    "        return sumvalue\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if root == None:\n",
    "            return False\n",
    "        node = root \n",
    "        node_arr = [root]\n",
    "        cur_sum = root.val \n",
    "        while node_arr:\n",
    "            while node.left:\n",
    "                node_arr.append(node.left)\n",
    "                node = node.left\n",
    "                cur_sum += node.val\n",
    "            if cur_sum == sum and node.left == None and node.right == None:\n",
    "                return True\n",
    "            while node.right == None:\n",
    "                p = node_arr.pop()\n",
    "                cur_sum -= p.val \n",
    "                if len(node_arr) == 0 :\n",
    "                   return False \n",
    "                node = node_arr[-1]\n",
    "            tmp = node.right \n",
    "            node.right = None\n",
    "            node = tmp \n",
    "            cur_sum += node.val \n",
    "            node_arr.append(node)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def hasPathSum(self, root: TreeNode, sum_of_node: int) -> bool:\r\n",
    "        if root == None:\r\n",
    "            return False\r\n",
    "        if root.left == None and root.right == None:\r\n",
    "            if root.val == sum_of_node:\r\n",
    "                return True\r\n",
    "            else:\r\n",
    "                return False\r\n",
    "        #l = [[node,remainning_of_sum,is_leaf(True or False)]]\r\n",
    "        l = [[root, sum_of_node-root.val, False]] \r\n",
    "        while len(l) > 0:\r\n",
    "            current_node = l[-1][0]\r\n",
    "            remainning_of_sum = l[-1][1]\r\n",
    "            is_leaf = l[-1][2]\r\n",
    "            if current_node.left == None and\\\r\n",
    "                current_node.right == None:\r\n",
    "                if remainning_of_sum == 0 and is_leaf == True:\r\n",
    "                    return True\r\n",
    "                else:\r\n",
    "                    l.pop()\r\n",
    "                    if len(l) != 0:\r\n",
    "                        if l[-1][0].left != None:\r\n",
    "                            l[-1][0].left = None\r\n",
    "                            continue\r\n",
    "                        elif l[-1][0].right != None:\r\n",
    "                            l[-1][0].right = None\r\n",
    "                            continue\r\n",
    "            else:\r\n",
    "                if current_node.left != None:\r\n",
    "                    next_node = current_node.left\r\n",
    "                    if next_node.left == None and next_node.right == None:\r\n",
    "                        next_is_leaf = True\r\n",
    "                    else:\r\n",
    "                        next_is_leaf = False\r\n",
    "                    next_remainning_of_sum =\\\r\n",
    "                        l[-1][1] - next_node.val\r\n",
    "                    l.append([next_node, next_remainning_of_sum, next_is_leaf])\r\n",
    "                    continue\r\n",
    "                else:\r\n",
    "                    next_node = current_node.right\r\n",
    "                    if next_node.left == None and next_node.right == None:\r\n",
    "                        next_is_leaf = True\r\n",
    "                    else:\r\n",
    "                        next_is_leaf = False\r\n",
    "                    next_remainning_of_sum =\\\r\n",
    "                        l[-1][1] - next_node.val\r\n",
    "                    l.append([next_node, next_remainning_of_sum, next_is_leaf])\r\n",
    "                    continue\r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        de = [(root, sum-root.val)]\n",
    "\n",
    "        while de:\n",
    "            cur, cursum = de.pop()\n",
    "            if not cur.left and not cur.right and cursum == 0:\n",
    "                return True\n",
    "            if cur.left:\n",
    "                de.append((cur.left, cursum - cur.left.val))\n",
    "            if cur.right:\n",
    "                de.append((cur.right, cursum - cur.right.val))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if not root: return False\n",
    "        l = root.left\n",
    "        r = root.right\n",
    "        val = root.val\n",
    "        if not l and not r:\n",
    "            return val == sum\n",
    "        return  self.hasPathSum(l, sum - val) or self.hasPathSum(r, sum - val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if root.val == sum:\n",
    "            if not root.left and not root.right:\n",
    "                return True\n",
    "        sum -= root.val\n",
    "        l = self.hasPathSum(root.left, sum)\n",
    "        r = self.hasPathSum(root.right, sum)\n",
    "        return l or r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if sum == root.val and root.left is None and root.right is None:\n",
    "            return True\n",
    "        return (self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if not root:return False\n",
    "        if not root.left and not root.right: #叶子节点\n",
    "            return sum == root.val\n",
    "        l = self.hasPathSum(root.left, sum-root.val)\n",
    "        r = self.hasPathSum(root.right, sum-root.val)\n",
    "        return l or r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root:\n",
    "        #     return False\n",
    "        # if not root.left and not root.right: #为叶子节点时\n",
    "        #     return sum == root.val\n",
    "        # sum -= root.val\n",
    "        # return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, sum: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        nodes = collections.deque([root])\n",
    "        vals = collections.deque([root.val])\n",
    "        while nodes:\n",
    "            node = nodes.popleft()\n",
    "            val = vals.popleft()\n",
    "            if not node.left and not node.right:\n",
    "                if val == sum:\n",
    "                    return True\n",
    "                    continue\n",
    "            if node.left:\n",
    "                nodes.append(node.left)\n",
    "                vals.append(val + node.left.val)\n",
    "            if node.right:\n",
    "                nodes.append(node.right)\n",
    "                vals.append(val + node.right.val)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: TreeNode, s: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if root.left is None and root.right is None:\n",
    "            return s == root.val\n",
    "        return self.hasPathSum(root.left, s - root.val) or self.hasPathSum(root.right, s - root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "\n",
    "        def recursion(pathSum, subroot):\n",
    "            if subroot.left == None and subroot.right == None:\n",
    "                if (pathSum + subroot.val) == targetSum:\n",
    "                    match.append(1)\n",
    "                    print(match)\n",
    "                    return\n",
    "            \n",
    "            pathSum += subroot.val\n",
    "            if subroot.left:\n",
    "                recursion(pathSum, subroot.left)\n",
    "            if subroot.right:\n",
    "                recursion(pathSum, subroot.right)\n",
    "            pathSum -= subroot.val\n",
    "        # debug  root = None\n",
    "        if not root: return False\n",
    "        pathSum = 0\n",
    "        match = []\n",
    "        recursion(pathSum, root)\n",
    "        if match:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if root == None:\n",
    "            return False\n",
    "        if root.left == None and root.right == None:\n",
    "            return targetSum == root.val\n",
    "        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减\n",
    "class Solution:\n",
    "    # 递归、递减\n",
    "    # def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "    #     def getPathSum(root, target):\n",
    "    #         if not root.left and not root.right:\n",
    "    #             if root.val == target:\n",
    "    #                 return True\n",
    "    #             else:\n",
    "    #                 return False\n",
    "    #         target -= root.val\n",
    "    #         if root.left:\n",
    "    #             if getPathSum(root.left, target):\n",
    "    #                 return True\n",
    "    #         if root.right:\n",
    "    #             if getPathSum(root.right, target):\n",
    "    #                 return True\n",
    "    #         return False\n",
    "        \n",
    "    #     if root == None:\n",
    "    #         return False\n",
    "    #     result = getPathSum(root, targetSum)\n",
    "    #     return result\n",
    "\n",
    "    # 递归、递加\n",
    "    # def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "    #     def getPathSum(root, sum):\n",
    "    #         nonlocal targetSum\n",
    "    #         if not root.left and not root.right:\n",
    "    #             sum += root.val\n",
    "    #             if sum == targetSum:\n",
    "    #                 return True\n",
    "    #             else:\n",
    "    #                 return False\n",
    "    #         sum += root.val\n",
    "    #         if root.left:\n",
    "    #             if getPathSum(root.left, sum):\n",
    "    #                 return True\n",
    "    #         if root.right:\n",
    "    #             if getPathSum(root.right, sum):\n",
    "    #                 return True\n",
    "    #         return False\n",
    "    #     if root== None:\n",
    "    #         return False\n",
    "    #     result = getPathSum(root, 0)\n",
    "    #     return result\n",
    "\n",
    "    # 迭代法\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if root == None:\n",
    "            return False\n",
    "        st = [(root, [], targetSum)]\n",
    "        while st:\n",
    "            cur, path, target = st.pop()\n",
    "            path.append(cur.val)\n",
    "            target -= cur.val\n",
    "            if target == 0 and not cur.left and not cur.right:\n",
    "                return True\n",
    "            if cur.left:\n",
    "                st.append((cur.left, path[:], target))\n",
    "            if cur.right:\n",
    "                st.append((cur.right, path[:], target))\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        stack = []\n",
    "        r = None\n",
    "        p = root\n",
    "        sum = 0\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                sum += p.val\n",
    "                if sum == targetSum and p.left is None and p.right is None:\n",
    "                    return True\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack[-1]\n",
    "            if p.right and r != p.right:\n",
    "                p = p.right\n",
    "                \n",
    "            else:\n",
    "                stack.pop()\n",
    "                r = p\n",
    "                sum -= p.val\n",
    "                p = None\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "       \n",
    "        if not root:return False\n",
    "        if not root.left and not root.right:\n",
    "            return targetSum==root.val\n",
    "\n",
    "        return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root, targetSum: int) -> bool:\n",
    "        res = []\n",
    "        def rec(root, target):\n",
    "            nonlocal res\n",
    "            if  not root :\n",
    "                return 0\n",
    "            res.append(root.val)\n",
    "            if not root.left  and not root.right:\n",
    "                if sum(res)== target:\n",
    "                    return 1\n",
    "                res.pop()\n",
    "                return 0\n",
    "            size = len(res)\n",
    "            if  rec(root.left, target):\n",
    "\n",
    "                return 1\n",
    "            res = res[:size]\n",
    "            if rec(root.right, target):\n",
    "                return 1\n",
    "\n",
    "            return 0\n",
    "        bo = rec(root,targetSum)\n",
    "        print(res)\n",
    "        return bo == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, res: list, path: list):\n",
    "        if root is None:\n",
    "            return\n",
    "        path.append(root.val)\n",
    "        if root.left is None and root.right is None:\n",
    "            res.append(path[:])\n",
    "            return\n",
    "        if root.left:\n",
    "            self.dfs(root.left, res, path)\n",
    "            path.pop(-1)\n",
    "        if root.right:\n",
    "            self.dfs(root.right, res, path)\n",
    "            path.pop(-1)\n",
    "    \n",
    "    def hasPathSum(self, root, targetSum: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        res = []\n",
    "        self.dfs(root, res, [])\n",
    "        for path in res:\n",
    "            if sum(path) == targetSum:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def hasPathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root: return False\n",
    "        if not root.left and not root.right:\n",
    "            return sum == root.val\n",
    "        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        #叶子节点 是指没有子节点的节点\n",
    "        #递归遍历一个个加，只要加到最后值=target，就返回True，否则false\n",
    "\n",
    "        \n",
    "        if not root:\n",
    "            return False\n",
    "\n",
    "        def dfs (root , target , path):\n",
    "            if not root :\n",
    "                return False\n",
    "            \n",
    "            if sum(path) == targetSum and not root.left and not root.right:\n",
    "                return True\n",
    "\n",
    "            l , r=False , False  #初始都为假\n",
    "            if root.left:\n",
    "                l=dfs(root.left , targetSum ,  path + [root.left.val]  )\n",
    "            if root.right:\n",
    "                r=dfs(root.right , targetSum ,  path + [root.right.val]  )\n",
    "            return l or r #有一个为True就是真\n",
    "\n",
    "\n",
    "        return dfs( root , targetSum , [root.val] )\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if root is None:\n",
    "            return False        \n",
    "        if root.left is None and root.right is None: # 叶子节点\n",
    "            return root.val == targetSum\n",
    "        if root.left is None:\n",
    "            return self.hasPathSum(root.right, targetSum-root.val)\n",
    "        if root.right is None:\n",
    "            return self.hasPathSum(root.left, targetSum-root.val)\n",
    "        if root.left and root.right:\n",
    "            return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
